package Leetcode.图;


import java.util.Arrays;

/**
 * @Author: kirito
 * @Date: 2024/9/14 17:28
 * @Description:
 * 有 n 个网络节点，标记为 1 到 n。
 *
 * 给你一个列表 times，表示信号经过 有向 边的传递时间。 times[i] = (ui, vi, wi)，其中 ui 是源节点，vi 是目标节点，
 * wi 是一个信号从源节点传递到目标节点的时间。
 *
 * 现在，从某个节点 K 发出一个信号。需要多久才能使所有节点都收到信号？如果不能使所有节点收到信号，返回 -1 。
 *
 * 输入：times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2
 * 输出：2
 */

public class 网络延迟时间 {

    public int networkDelayTime(int[][] times, int n, int k) {
        // 定义一个足够大的数作为无穷大，防止在计算过程中发生整数溢出
        final int INF = Integer.MAX_VALUE / 2;
        // 创建一个邻接矩阵来表示图，大小为n x n
        int[][] graph = new int[n][n];
        // 初始化邻接矩阵，所有边的权重初始为无穷大
        for (int[] row : graph) {
            Arrays.fill(row, INF);
        }
        // 根据输入的时间数组，填充邻接矩阵  有向图
        for (int[] t : times) {
            graph[t[0] - 1][t[1] - 1] = t[2];
        }

        // 初始化最大距离为0
        int maxDis = 0;
        // 创建一个数组来存储从起点k到其他所有点的最短距离
        int[] dist = new int[n];
        // 初始化最短距离数组，所有点的最短距离初始为无穷大
        Arrays.fill(dist, INF);
        // 起点到起点的最短距离为0
        dist[k - 1] = 0;
        // 创建一个布尔数组来标记哪些点的最短路径已经确定
        boolean[] done = new boolean[n];

        // 使用Dijkstra算法寻找最短路径
        while (true) {
            // 初始化未处理的最短距离节点索引
            int x = -1;
            // 遍历所有节点，找到当前未处理的最短距离节点
            for (int i = 0; i < n; i++) {
                if (!done[i] && (x < 0 || dist[i] < dist[x])) {
                    x = i;
                }
            }
            // 如果所有节点的最短路径都已确定，则退出循环
            if (x < 0) {
                return maxDis; // 最后一次计算出的最短路径即为最大值
            }
            // 如果当前节点的最短距离仍为无穷大，说明该节点无法到达
            if (dist[x] == INF) {
                return -1; // 有节点无法到达
            }
            // 更新最大距离
            maxDis = dist[x]; // 求出的最短路径会越来越大
            // 标记当前节点的最短路径已经确定
            done[x] = true; // 最短路径已经确定，无法变得更短
            // 更新当前节点的邻居节点的最短路径
            for (int i = 0; i < n; i++) {
                // 如果从当前节点到邻居节点的距离加上当前节点的最短距离小于当前邻居节点的最短距离，则更新
                dist[i] = Math.min(dist[i], dist[x] + graph[x][i]);
            }
        }
    }

}
